Cellular automata (CA) have been found as an attractive modeling tool forvarious applications, such as, pattern recognition, image processing, datacompression, encryption, and specially for VLSI design & test. For suchapplications, mostly a special class of CA, called as linear/additive CA, havebeen utilized. Since linear/additive CA refer a limited number of candidate CA,while searching for solution to a problem, the best result may not be expected.The nonlinear CA can be a better alternative to linear/additive CA forachieving desired solutions in different applications. However, the nonlinearCA are yet to be characterized to fit the design for modeling an application.This work targets characterization of the nonlinear CA to utilize the hugesearch space of nonlinear CA while developing applications in VLSI domain. Ananalytical framework is developed to explore the properties of CA rules. Thecharacterization is directed to deal with the reversibility, as the reversibleCA are primarily targeted for VLSI applications. The reported characterizationenables us to design two algorithms of linear time complexities -- one foridentification and nother for synthesis of nonlinear reversible CA. Finally,the CA rules are classified into 6 classes for developing further efficientsynthesis algorithm.
展开▼
